package com.company.algo.tree.BST;

import com.company.algo.pojo.TreeNode;

/**
 * 力扣第 230 题「二叉搜索树中第K小的元素」
 * 考虑搜索树的特征：中序遍历的结果为递增
 */
public class KthSmallest {
    /*int kthSmallest(TreeNode root, int k) {
        traverse(root,k);
        return res;
    }
    int res = 0;
    int rank = 0;
    void traverse(TreeNode root, int k){
        if (root == null) return;
        traverse(root.left,k);
        rank++;
        if (k == rank){
            res = root.val;
            return;
        }
        traverse(root.right,k);
    }*/

    int res = -1;
    int k = 0;
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        traverse(root);
        return res;
    }

    void traverse(TreeNode root){
        if(root == null) return;
        traverse(root.left);
        if(--k == 0) {
            res = root.val;
            return;
        }
        traverse(root.right);
    }


    public static void main(String[] args) {
        KthSmallest Main = new KthSmallest();
        TreeNode root = new TreeNode(3);
        TreeNode l1 = new TreeNode(1);
        TreeNode r1 = new TreeNode(4);
        TreeNode lr1 = new TreeNode(2);
        root.left = l1;
        root.right = r1;
        l1.right = lr1;
        System.out.println(Main.kthSmallest(root, 1));
    }
}
